// 474. 一和零
// 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

// 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

// 示例 1：

// 输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
// 输出：4
// 解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
// 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意
// ，因为它含 4 个 1 ，大于 n 的值 3 。
// 思路：转换了背包问题，m(i) n(j)相当于两个维度  公式dp[i - zeroNum][j - oneNum] + 1
// 循环遍历每一个物品(字符串)，算出里面有多少个0和1 然后遍历背包 从后往前获取最大值 
/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
 var findMaxForm = function(strs, m, n) {
    const dp = Array.from(Array(m+1), () => Array(n+1).fill(0));
    let numOfZeros, numOfOnes;
    for(let str of strs){
        numOfZeros=0,numOfOnes=0;
        for(let c of str){// 遍历物品
            if(c==='0'){
                numOfZeros++;
            }else{
                numOfOnes++;
            }
        }
        for(let i=m;i>=numOfZeros;i--){// 遍历背包容量且从后向前遍历！
            for(let j=n;j>=numOfOnes;j--){
                dp[i][j]=Math.max(dp[i][j],dp[i-numOfZeros][j-numOfOnes]+1)
            }
        }
    }
    
    return dp[m][n];
};